package leetcode.D100.T32;

class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        for (int i=1; i<s.length(); ++i) {
            if (s.charAt(i) == ')') {
                if (i > 0) {
                    if (s.charAt(i-1) == '(')
                        dp[i] = i > 1 ? dp[i-2] + 2 : 2;
                    else {
                        int j = i - 1 - dp[i-1];
                        if (j >= 0) {
                            if (s.charAt(j) == '(') {
                                dp[i] = j > 0 ? dp[j-1] + i - j + 1 : i + 1;
                            }
                        }
                    }
                }
            }
        }
        int res = 0;
        for (int i=0; i<dp.length; ++i) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
